DSC 40B – Theoretical Foundations of Data Science II
Problems tagged with "topological sorting"
Problem #113
Tags: topological sorting
Consider the graph \(G = (V, E)\) with \(V = \{a, b, c\}\) and \(E = \{(a, b)\}\).
How many valid topological sorts of this graph are there?
Solution
3
Problem #160
Tags: topological sorting
Let \(G = (V,E)\) be the directed graph with \(V = \{a, b, c, d, e\}\) and \(E = \{(a, b), (a, c), (a, d), (b, e), (c, e), (d, e)\}\). How many valid topological sorts of $V$ are there?
Solution
6